package leetcode;

/**
 * 109. 有序链表转换二叉搜索树
 * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
 * <p>
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * <p>
 * <p>
 * 输入: head = [-10,-3,0,5,9]
 * 输出: [0,-3,9,-10,null,5]
 * 解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
 * 示例 2:
 * <p>
 * 输入: head = []
 * 输出: []
 */
public class SortedListToBST {

    public TreeNode sortedListToBST(ListNode head) {
        return post(head, null);
    }


    public TreeNode post(ListNode head, ListNode tail) {

        if (head == tail) {
            return null;
        }

        ListNode mid = getMid(head, tail);
        TreeNode root = new TreeNode(mid.val);

        root.left = post(head, mid);
        root.right = post(mid.next, tail);

        return root;
    }

    public ListNode getMid(ListNode head, ListNode tail) {

        ListNode fast = head;
        ListNode slow = head;
        // tail 会挡住 不需要判空
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
}
